package Offer;

public class QuickSort {
    public int[] quickSort(int[] arr) {
        __quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    private void __quickSort(int[] arr, int left, int right) {
        if (left > right)
            return;
        //这里i不能设定为left+1，因为可能子数组只有一个数
        int i = left , j = right;
        int temp = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= temp) {
                j--;
            }

            while (i < j && arr[i] <= temp) {
                i++;
            }

            if (i < j) {
                int swap = arr[i];
                arr[i] = arr[j];
                arr[j] = swap;
                //这里一定不要增加和减少
//                i++;
//                j--;
            }
        }
        //最后i和j一定是相等的，因为while循环里，先从右边找比自己小的数，再从左边找比自己大的数。保证不会卡住！（保证最后与temp交换的时候，i或j对应的数是比temp要小的）
        arr[left] = arr[i];
        arr[i] = temp;
        __quickSort(arr, left, j - 1);
        __quickSort(arr, j + 1, right);


    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] arr = {4, 322, 45, 123, 87, 235, 98, 235, 0, 32, 98, 23, 322, 1237, 728634, 2374, 234, 123, 6473};
        quickSort.quickSort(arr);
        for (int a : arr) {
            System.out.print(a + ",");
        }
    }
}
